Secure k-Nearest Neighbor Query over Encrypted Data in Outsourced Environments

摘要

For the past decade, query processing on relational data has been studiedextensively, and many theoretical and practical solutions to query processinghave been proposed under various scenarios. With the recent popularity of cloudcomputing, users now have the opportunity to outsource their data as well asthe data management tasks to the cloud. However, due to the rise of variousprivacy issues, sensitive data (e.g., medical records) need to be encryptedbefore outsourcing to the cloud. In addition, query processing tasks should behandled by the cloud; otherwise, there would be no point to outsource the dataat the first place. To process queries over encrypted data without the cloudever decrypting the data is a very challenging task. In this paper, we focus onsolving the k-nearest neighbor (kNN) query problem over encrypted databaseoutsourced to a cloud: a user issues an encrypted query record to the cloud,and the cloud returns the k closest records to the user. We first present abasic scheme and demonstrate that such a naive solution is not secure. Toprovide better security, we propose a secure kNN protocol that protects theconfidentiality of the data, user's input query, and data access patterns.Also, we empirically analyze the efficiency of our protocols through variousexperiments. These results indicate that our secure protocol is very efficienton the user end, and this lightweight scheme allows a user to use any mobiledevice to perform the kNN query.